В игре "Города" последовательно называют города, при этом каждый следующий город должен начинаться на букву, которой заканчивается предыдущий город. Запрещено повторять название городов. Например, сначала была названа "Москва" - заканчивается на "а", следует назвать другой город, у которого в названии первая буква "а". Это может быть "Архангельск". Следующий город должен начинаться на "к" и т.д. Дан список городов России:
КЕМЕРОВО АРЗАМАС САМАРА КИРОВ ОРСК КАЛУГА АРХАНГЕЛЬСК КОВРОВ ВЛАДИВОСТОК ВОРОНЕЖ АЛУШТА КАЛИНИН НОВГОРОД САНКТ-ПЕТЕРБУРГ НИЖНЕВАРТОВСК ТАМБОВ МОСКВА МУРОМ КУРСК АБАКАН НОРИЛЬСК СМОЛЕНСК ЖУКОВ ГЛАЗОВ ДЕРБЕНТ
Необходимо определить максимально возможную последовательность, которую можно составить из данного перечня и перечислить названия городов (может быть несколько вариантов решения)
В игре "Города" последовательно называют города, при этом каждый следующий город должен начинаться на букву, которой заканчивается предыдущий город. Запрещено повторять название городов. Например, сначала была названа "Москва" - заканчивается на "а", следует назвать другой город, у которого в названии первая буква "а". Это может быть "Архангельск". Следующий город должен начинаться на "к" и т.д. Дан список городов России:
КЕМЕРОВО АРЗАМАС САМАРА КИРОВ ОРСК КАЛУГА АРХАНГЕЛЬСК КОВРОВ ВЛАДИВОСТОК ВОРОНЕЖ АЛУШТА КАЛИНИН НОВГОРОД САНКТ-ПЕТЕРБУРГ НИЖНЕВАРТОВСК ТАМБОВ МОСКВА МУРОМ КУРСК АБАКАН НОРИЛЬСК СМОЛЕНСК ЖУКОВ ГЛАЗОВ ДЕРБЕНТ
Необходимо определить максимально возможную последовательность, которую можно составить из данного перечня и перечислить названия городов (может быть несколько вариантов решения)MCH
Все равно как, хоть в уме. "Мозговой штурм" это ведь не обязательно формульная оптимизация. Как это реализовать формулами не знаю, но будет интересно посмотреть на чью нибудь реализацию
Все равно как, хоть в уме. "Мозговой штурм" это ведь не обязательно формульная оптимизация. Как это реализовать формулами не знаю, но будет интересно посмотреть на чью нибудь реализацию
Формулами? А варианты - протяжкой этой формулы, например, вниз?
Всего возможно 495687 вариантов составления различных последовательностей, из которых 8064 имеют максимальную длину.
Реализовал перебор всех возможных вариантов формулами с использованием доп. ячеек Не стал выводить все варианты на лист, т.к. файл получается очень тяжелым и долго пересчитывается. (файл пока не выкладываю)
Формулами? А варианты - протяжкой этой формулы, например, вниз?
Всего возможно 495687 вариантов составления различных последовательностей, из которых 8064 имеют максимальную длину.
Реализовал перебор всех возможных вариантов формулами с использованием доп. ячеек Не стал выводить все варианты на лист, т.к. файл получается очень тяжелым и долго пересчитывается. (файл пока не выкладываю)MCH
Насколько я себе представляю алгоритм решения задачи, то он сродни игре в шахматы, где на каждый ход надо просчитать все возможные варианты его "последствий". При выборе каждого последующего слова надо учитывать какая последующая цепочка будет максимальной, причем начинать это делать с первого же слова Думаю что одной формулой сделать этого не получится, учитывая ограничения Excel, да и по идее формула должна быть итеративной С доп столбцами делать не интересно, т. к. Михаил уже сделал и вряд ли сделал неправильно
Насколько я себе представляю алгоритм решения задачи, то он сродни игре в шахматы, где на каждый ход надо просчитать все возможные варианты его "последствий". При выборе каждого последующего слова надо учитывать какая последующая цепочка будет максимальной, причем начинать это делать с первого же слова Думаю что одной формулой сделать этого не получится, учитывая ограничения Excel, да и по идее формула должна быть итеративной С доп столбцами делать не интересно, т. к. Михаил уже сделал и вряд ли сделал неправильно Serge_007
Насколько я себе представляю алгоритм решения задачи, то он сродни игре в шахматы, где на каждый ход надо просчитать все возможные варианты его "последствий"
На самом деле, всё проще - это задачка на нахождение, эм-м-м... "максимальной длины простого пути направленного графа" или "максимальной простой цепи простого орграфа", типа того... А задачка эта (в отличие от нахождения минимальных/кратчайших путей) - либо NP-полная, либо на ДП решаемая за O(n3), и даже волновой метод - не панацея. Потому что граф у нас может содержать циклы, а также быть многокомпонентным (по связности). И это кодом (т.е. с предварительным составлением матрицы/списка смежности), плюс затраты памяти минимум на две матрицы n2. Так что про формулы я вообще молчу - либо вирт.массивы (или доп.ячейки) будут немерено кушать ресурсы, либо расчёты будут бешеными, особенно при использовании чисто матричного подхода (с МУМНОЖ() в степени, например)...
Насколько я себе представляю алгоритм решения задачи, то он сродни игре в шахматы, где на каждый ход надо просчитать все возможные варианты его "последствий"
На самом деле, всё проще - это задачка на нахождение, эм-м-м... "максимальной длины простого пути направленного графа" или "максимальной простой цепи простого орграфа", типа того... А задачка эта (в отличие от нахождения минимальных/кратчайших путей) - либо NP-полная, либо на ДП решаемая за O(n3), и даже волновой метод - не панацея. Потому что граф у нас может содержать циклы, а также быть многокомпонентным (по связности). И это кодом (т.е. с предварительным составлением матрицы/списка смежности), плюс затраты памяти минимум на две матрицы n2. Так что про формулы я вообще молчу - либо вирт.массивы (или доп.ячейки) будут немерено кушать ресурсы, либо расчёты будут бешеными, особенно при использовании чисто матричного подхода (с МУМНОЖ() в степени, например)...AndreTM
Skype: andre.tm.007 Donate: Qiwi: 9517375010
Сообщение отредактировал AndreTM - Четверг, 06.02.2014, 02:32
Попробовал решить задачу в лоб, к сожалению SQL не дает больше 13 полей. Запрос выполнялся 8 мин. вместе с выводом данных.
[vba]
Код
SELECT г1.F1 AS F1, г2.F1 AS F2, г3.F1 AS F3, г4.F1 AS F4, г5.F1 AS F5, г6.F1 AS F6, г7.F1 AS F7, г8.F1 AS F8, г9.F1 AS F9, г10.F1 AS F10, г11.F1 AS F11, г12.F1 AS F12, г13.F1 AS F13 FROM [Лист1$1:25] AS г1, [Лист1$1:25] AS г2, [Лист1$1:25] AS г3, [Лист1$1:25] AS г4, [Лист1$1:25] AS г5, [Лист1$1:25] AS г6, [Лист1$1:25] AS г7, [Лист1$1:25] AS г8, [Лист1$1:25] AS г9, [Лист1$1:25] AS г10, [Лист1$1:25] AS г11, [Лист1$1:25] AS г12, [Лист1$1:25] AS г13 WHERE right(г1.F1,1) = left(г2.F1,1) AND right(г2.F1,1) = left(г3.F1,1) AND right(г3.F1,1) = left(г4.F1,1) AND right(г4.F1,1) = left(г5.F1,1) AND right(г5.F1,1) = left(г6.F1,1) AND right(г6.F1,1) = left(г7.F1,1) AND right(г7.F1,1) = left(г8.F1,1) AND right(г8.F1,1) = left(г9.F1,1) AND right(г9.F1,1) = left(г10.F1,1) AND right(г10.F1,1) = left(г11.F1,1) AND right(г11.F1,1) = left(г12.F1,1) AND right(г12.F1,1) = left(г13.F1,1) AND г1.F1 <> г2.F1 AND г1.F1 <> г2.F1 AND г1.F1 <> г3.F1 AND г1.F1 <> г4.F1 AND г1.F1 <> г5.F1 AND г1.F1 <> г6.F1 AND г1.F1 <> г7.F1 AND г1.F1 <> г8.F1 AND г1.F1 <> г9.F1 AND г1.F1 <> г10.F1 AND г1.F1 <> г11.F1 AND г1.F1 <> г12.F1 AND г1.F1 <> г13.F1 AND г2.F1 <> г3.F1 AND г2.F1 <> г4.F1 AND г2.F1 <> г5.F1 AND г2.F1 <> г6.F1 AND г2.F1 <> г7.F1 AND г2.F1 <> г8.F1 AND г2.F1 <> г9.F1 AND г2.F1 <> г10.F1 AND г2.F1 <> г11.F1 AND г2.F1 <> г12.F1 AND г2.F1 <> г13.F1 AND г3.F1 <> г4.F1 AND г3.F1 <> г5.F1 AND г3.F1 <> г6.F1 AND г3.F1 <> г7.F1 AND г3.F1 <> г8.F1 AND г3.F1 <> г9.F1 AND г3.F1 <> г10.F1 AND г3.F1 <> г11.F1 AND г3.F1 <> г12.F1 AND г3.F1 <> г13.F1 AND г4.F1 <> г5.F1 AND г4.F1 <> г6.F1 AND г4.F1 <> г7.F1 AND г4.F1 <> г8.F1 AND г4.F1 <> г9.F1 AND г4.F1 <> г10.F1 AND г4.F1 <> г11.F1 AND г4.F1 <> г12.F1 AND г4.F1 <> г13.F1 AND г5.F1 <> г6.F1 AND г5.F1 <> г7.F1 AND г5.F1 <> г8.F1 AND г5.F1 <> г9.F1 AND г5.F1 <> г10.F1 AND г5.F1 <> г11.F1 AND г5.F1 <> г12.F1 AND г5.F1 <> г13.F1 AND г6.F1 <> г7.F1 AND г6.F1 <> г8.F1 AND г6.F1 <> г9.F1 AND г6.F1 <> г10.F1 AND г6.F1 <> г11.F1 AND г6.F1 <> г12.F1 AND г6.F1 <> г13.F1 AND г7.F1 <> г8.F1 AND г7.F1 <> г9.F1 AND г7.F1 <> г10.F1 AND г7.F1 <> г11.F1 AND г7.F1 <> г12.F1 AND г7.F1 <> г13.F1 AND г8.F1 <> г9.F1 AND г8.F1 <> г10.F1 AND г8.F1 <> г11.F1 AND г8.F1 <> г12.F1 AND г8.F1 <> г13.F1 AND г9.F1 <> г10.F1 AND г9.F1 <> г11.F1 AND г9.F1 <> г12.F1 AND г9.F1 <> г13.F1 AND г10.F1 <> г11.F1 AND г10.F1 <> г12.F1 AND г10.F1 <> г13.F1 AND г11.F1 <> г12.F1 AND г11.F1 <> г13.F1 AND г12.F1 <> г13.F1
[/vba]
Попробовал решить задачу в лоб, к сожалению SQL не дает больше 13 полей. Запрос выполнялся 8 мин. вместе с выводом данных.
[vba]
Код
SELECT г1.F1 AS F1, г2.F1 AS F2, г3.F1 AS F3, г4.F1 AS F4, г5.F1 AS F5, г6.F1 AS F6, г7.F1 AS F7, г8.F1 AS F8, г9.F1 AS F9, г10.F1 AS F10, г11.F1 AS F11, г12.F1 AS F12, г13.F1 AS F13 FROM [Лист1$1:25] AS г1, [Лист1$1:25] AS г2, [Лист1$1:25] AS г3, [Лист1$1:25] AS г4, [Лист1$1:25] AS г5, [Лист1$1:25] AS г6, [Лист1$1:25] AS г7, [Лист1$1:25] AS г8, [Лист1$1:25] AS г9, [Лист1$1:25] AS г10, [Лист1$1:25] AS г11, [Лист1$1:25] AS г12, [Лист1$1:25] AS г13 WHERE right(г1.F1,1) = left(г2.F1,1) AND right(г2.F1,1) = left(г3.F1,1) AND right(г3.F1,1) = left(г4.F1,1) AND right(г4.F1,1) = left(г5.F1,1) AND right(г5.F1,1) = left(г6.F1,1) AND right(г6.F1,1) = left(г7.F1,1) AND right(г7.F1,1) = left(г8.F1,1) AND right(г8.F1,1) = left(г9.F1,1) AND right(г9.F1,1) = left(г10.F1,1) AND right(г10.F1,1) = left(г11.F1,1) AND right(г11.F1,1) = left(г12.F1,1) AND right(г12.F1,1) = left(г13.F1,1) AND г1.F1 <> г2.F1 AND г1.F1 <> г2.F1 AND г1.F1 <> г3.F1 AND г1.F1 <> г4.F1 AND г1.F1 <> г5.F1 AND г1.F1 <> г6.F1 AND г1.F1 <> г7.F1 AND г1.F1 <> г8.F1 AND г1.F1 <> г9.F1 AND г1.F1 <> г10.F1 AND г1.F1 <> г11.F1 AND г1.F1 <> г12.F1 AND г1.F1 <> г13.F1 AND г2.F1 <> г3.F1 AND г2.F1 <> г4.F1 AND г2.F1 <> г5.F1 AND г2.F1 <> г6.F1 AND г2.F1 <> г7.F1 AND г2.F1 <> г8.F1 AND г2.F1 <> г9.F1 AND г2.F1 <> г10.F1 AND г2.F1 <> г11.F1 AND г2.F1 <> г12.F1 AND г2.F1 <> г13.F1 AND г3.F1 <> г4.F1 AND г3.F1 <> г5.F1 AND г3.F1 <> г6.F1 AND г3.F1 <> г7.F1 AND г3.F1 <> г8.F1 AND г3.F1 <> г9.F1 AND г3.F1 <> г10.F1 AND г3.F1 <> г11.F1 AND г3.F1 <> г12.F1 AND г3.F1 <> г13.F1 AND г4.F1 <> г5.F1 AND г4.F1 <> г6.F1 AND г4.F1 <> г7.F1 AND г4.F1 <> г8.F1 AND г4.F1 <> г9.F1 AND г4.F1 <> г10.F1 AND г4.F1 <> г11.F1 AND г4.F1 <> г12.F1 AND г4.F1 <> г13.F1 AND г5.F1 <> г6.F1 AND г5.F1 <> г7.F1 AND г5.F1 <> г8.F1 AND г5.F1 <> г9.F1 AND г5.F1 <> г10.F1 AND г5.F1 <> г11.F1 AND г5.F1 <> г12.F1 AND г5.F1 <> г13.F1 AND г6.F1 <> г7.F1 AND г6.F1 <> г8.F1 AND г6.F1 <> г9.F1 AND г6.F1 <> г10.F1 AND г6.F1 <> г11.F1 AND г6.F1 <> г12.F1 AND г6.F1 <> г13.F1 AND г7.F1 <> г8.F1 AND г7.F1 <> г9.F1 AND г7.F1 <> г10.F1 AND г7.F1 <> г11.F1 AND г7.F1 <> г12.F1 AND г7.F1 <> г13.F1 AND г8.F1 <> г9.F1 AND г8.F1 <> г10.F1 AND г8.F1 <> г11.F1 AND г8.F1 <> г12.F1 AND г8.F1 <> г13.F1 AND г9.F1 <> г10.F1 AND г9.F1 <> г11.F1 AND г9.F1 <> г12.F1 AND г9.F1 <> г13.F1 AND г10.F1 <> г11.F1 AND г10.F1 <> г12.F1 AND г10.F1 <> г13.F1 AND г11.F1 <> г12.F1 AND г11.F1 <> г13.F1 AND г12.F1 <> г13.F1
А задачка эта (в отличие от нахождения минимальных/кратчайших путей) - либо NP-полная, либо на ДП решаемая за O(n3)
Андрей, не знаю как данную задачу решать за O(n3), матрицу смежности построить легко, а что дальше? какая здесь динамика? Решал ее полным перебором, алгоритмом на подобии поиска в глубину на рекурсиях
А задачка эта (в отличие от нахождения минимальных/кратчайших путей) - либо NP-полная, либо на ДП решаемая за O(n3)
Андрей, не знаю как данную задачу решать за O(n3), матрицу смежности построить легко, а что дальше? какая здесь динамика? Решал ее полным перебором, алгоритмом на подобии поиска в глубину на рекурсияхMCH
Четыре доп.столбца по 25 ячеек, и один столбец для ответа
А формулы в доп.столбцах - не массивные, случаем?
Я формулами не стал решать. Ну просто потому, что задачки такого плана решать формулами не то, чтобы бессмысленно - но как-то некомильфовно А полные переборы (если кто не в курсе - NP) и рекурсии - они, как бы, чисто программистские и алгоритмические, а посему решаемы средствами любого ЯП. А там уже вступает в силу принцип экономии ресурсов (стандартный треугольник "память-проц-время"), и к Excel'ю это перестаёт иметь даже отдаленное отношение
И да (Михаилу) - нормальной динамики я так и не придумал, максимум - замена полной рекурсии на "двойную глубину", с предварительным переходом к псевдо-двойственному графу (т.е. замене рёбер на вершины, что дало возможность оперировать над конечным множеством символов алфавита в качестве вершин), но тогда всё упёрлось в вычисление всех циклов... И на объемах набора "городов" ниже пятого прорядка - проигрывая обычной тупой рекурсии...
Четыре доп.столбца по 25 ячеек, и один столбец для ответа
А формулы в доп.столбцах - не массивные, случаем?
Я формулами не стал решать. Ну просто потому, что задачки такого плана решать формулами не то, чтобы бессмысленно - но как-то некомильфовно А полные переборы (если кто не в курсе - NP) и рекурсии - они, как бы, чисто программистские и алгоритмические, а посему решаемы средствами любого ЯП. А там уже вступает в силу принцип экономии ресурсов (стандартный треугольник "память-проц-время"), и к Excel'ю это перестаёт иметь даже отдаленное отношение
И да (Михаилу) - нормальной динамики я так и не придумал, максимум - замена полной рекурсии на "двойную глубину", с предварительным переходом к псевдо-двойственному графу (т.е. замене рёбер на вершины, что дало возможность оперировать над конечным множеством символов алфавита в качестве вершин), но тогда всё упёрлось в вычисление всех циклов... И на объемах набора "городов" ниже пятого прорядка - проигрывая обычной тупой рекурсии...AndreTM
А там уже вступает в силу принцип экономии ресурсов (стандартный треугольник "память-проц-время")
При данном перечне городов, полный перебор всех (495687) вариантов занимает менее минуты (на моем ноуте - 22 секунды), так что задача вполне решаема перебором и не особо требовательна к ресурсам.
нормальной динамики я так и не придумал, максимум - замена полной рекурсии на "двойную глубину"...
Ответ на поставленный вопрос: "Необходимо определить максимально возможную последовательность, которую можно составить из данного перечня и перечислить названия городов" есть?
ИМХО, "Мозговой штурм" это не обязательно формулы, это может быть и решение на VBA или "поиском решения" или даже карандашом на листке бумаги (хотя данная задача не для формул, а для VBA)
А там уже вступает в силу принцип экономии ресурсов (стандартный треугольник "память-проц-время")
При данном перечне городов, полный перебор всех (495687) вариантов занимает менее минуты (на моем ноуте - 22 секунды), так что задача вполне решаема перебором и не особо требовательна к ресурсам.
нормальной динамики я так и не придумал, максимум - замена полной рекурсии на "двойную глубину"...
Ответ на поставленный вопрос: "Необходимо определить максимально возможную последовательность, которую можно составить из данного перечня и перечислить названия городов" есть?
ИМХО, "Мозговой штурм" это не обязательно формулы, это может быть и решение на VBA или "поиском решения" или даже карандашом на листке бумаги (хотя данная задача не для формул, а для VBA)MCH
Максимальная последовательность состоит из 20 городов
МУРОМ МОСКВА АРЗАМАС САМАРА АРХАНГЕЛЬСК КЕМЕРОВО ОРСК КИРОВ ВЛАДИВОСТОК КАЛУГА АЛУШТА АБАКАН НИЖНЕВАРТОВСК КУРСК КАЛИНИН НОВГОРОД ДЕРБЕНТ ТАМБОВ ВОРОНЕЖ ЖУКОВ
В файле решение макросом и формулами. Решение формулами реализовано перебором на итерациях с запоминанием максимальной (итерации должны быть включены). Для быстрого поиска наибольшей последовательности изменил порядок городов (если не менять, то поиск идет значительно дольше, но все равно находится) Для запуска необходимо ввести какое либо число в ячейку C2. Если раскрыть группировку в столбцах G:J, то будет видно как происходит перебор городов.
Максимальная последовательность состоит из 20 городов
МУРОМ МОСКВА АРЗАМАС САМАРА АРХАНГЕЛЬСК КЕМЕРОВО ОРСК КИРОВ ВЛАДИВОСТОК КАЛУГА АЛУШТА АБАКАН НИЖНЕВАРТОВСК КУРСК КАЛИНИН НОВГОРОД ДЕРБЕНТ ТАМБОВ ВОРОНЕЖ ЖУКОВ
В файле решение макросом и формулами. Решение формулами реализовано перебором на итерациях с запоминанием максимальной (итерации должны быть включены). Для быстрого поиска наибольшей последовательности изменил порядок городов (если не менять, то поиск идет значительно дольше, но все равно находится) Для запуска необходимо ввести какое либо число в ячейку C2. Если раскрыть группировку в столбцах G:J, то будет видно как происходит перебор городов.MCH
Выкладываю свое решение. "Поиск решения" подобрал максимальную цепочку в 19 городов, но с помощью хитрости я выудил у Миши название первого города и все стало на свои места.)
Выкладываю свое решение. "Поиск решения" подобрал максимальную цепочку в 19 городов, но с помощью хитрости я выудил у Миши название первого города и все стало на свои места.)ZORRO2005
МУРОМ МОСКВА АРЗАМАС САМАРА АРХАНГЕЛЬСК КАЛУГА АЛУШТА АБАКАН НОРИЛЬСК КАЛИНИН НОВГОРОД ДЕРБЕНТ ТАМБОВ ВЛАДИВОСТОК КЕМЕРОВО ОРСК КУРСК КИРОВ ВОРОНЕЖ ЖУКОВ
Вариант решения *карандашом*
МУРОМ МОСКВА АРЗАМАС САМАРА АРХАНГЕЛЬСК КАЛУГА АЛУШТА АБАКАН НОРИЛЬСК КАЛИНИН НОВГОРОД ДЕРБЕНТ ТАМБОВ ВЛАДИВОСТОК КЕМЕРОВО ОРСК КУРСК КИРОВ ВОРОНЕЖ ЖУКОВ