Как решать подобные задачи?
Вот знакомый спросил, может ли ему машина помочь решить головоломку. Сдуру сказал конечно же. Теперь дали порешать
Есть несколько пересекающихся перемещений
А:1,8,9,5,1
Б:1,5,9,8,1
С:1,5,4,3,2,1
Д:6,7,8,9,10,6
Есть также начальное состояние и конечное.
Задача - построить цепочку перемещений из начального состояния в конечное
Пример:
Начальное
Конечное
Перемещения
Д,Б,А
Поиск числа простых циклов графа.
https://en.wikipedia.org/wiki/Cycle_(graph_theory)#Cycle_d...
Простые циклы, как я понял. Хотя описание задачи так себе.
Это будет что-то вроде волнового алгоритма. Ведь все вершины графа связаны - гоним волну из одной, пока не достигнем нужной. По пути соблюдаем условия в зависимости от задачи - нельзя идти назад, нельзя проходить вершины или рёбра два раза, и т.п., что там может быть. Все ветки алгоритма, достигшие нужной вершины с соблюдением всех условий, и будут удовлетворять решению. Если условия не соблюдаются на любом этапе алгоритма, ветка останавливается.
Только поле не двухмерное, а любая случайная структура. Лучше тут, наверное. Разве что дерево замкнутое - локально (местные циклы) или полностью. Но замкнутым оно становится лишь когда дошли до вершины, в которой уже были, а так в принципе этому алгоритму должно быть всё равно, по какой структуре ходить - всё в основном определяется в условиях на каждой итерации.
Проще всего, наверное, рекурсией сделать, если граф не большой.
Я не понял что требуется
Похоже самый полезный коммент
Попробуем... Кубик рубика то знаешь. Вот что то типа этого только сильно проще и в 2Д.
Есть 3 оси вращения, показанные цветными стрелками в первом посте. Вместо цифр нарисованы картинки.
Вначале картинки разбросаны "случайным" образом, в задаче требуется их разместить в определенном порядке.
Нужен алгоритм который указывает как именно нужно вращать "кольца" чтобы разместить картинки в определенном порядке.
Давай тогда начинать с того что еще непонятно.
Чем и как определяется порядок?
В реальности - Начальная позиция вычисляется приложением для конкретного устройства/пользователя, конечная всегда остаётся фиксированной. /Картинка нарисована как должно быть./
Для расчётов - и начальная и конечная позиции задаются. В примерах это цифры на определённых местах
Можно даже попроще задание сделать, не нужны все повороты для перехода от исходной позиции к заданной.
Можно как в кубике Рубика, знать переходы для обмена двух элементов не стоящих на своем месте. Потому как поставить большинство позиций на правильные места можно относительно быстро вручную. Но вот постоянно два элемента остаются на неправильных позициях.
Как от этого
"Есть также начальное состояние и конечное.
Задача - построить цепочку перемещений из начального состояния в конечное"
перейти к этому
"Есть 3 оси вращения, показанные цветными стрелками в первом посте. Вместо цифр нарисованы картинки.
Вначале картинки разбросаны "случайным" образом, в задаче требуется их разместить в определенном порядке.
Нужен алгоритм который указывает как именно нужно вращать "кольца" чтобы разместить картинки в определенном порядке."
вот разбей кубик Рубика, а после сложи
А может это карточный пасьянс? Или домино? И на самом деле надо представить, что ты жонглёр, и ты подкидываешь доминошки в воздух. И вообще ты фокусник, а не жонглёр, поэтому доминошки падают назад в виде карт. И вот задача - как сделать так, чтобы они выпали в виде натюрморта из свехиж фруктов и сгнивших овощей.
Как от этого...перейти к этому...
Так не нужно переходить. Поначалу специально хотел абстрагироваться от конкретной задачи.
Если говорить про путь Эйлера, то необязательно переходить к мостам через реку. 
Но опять отвлечение. Теперь задача более понятна или еще нет?
Нет, не понятно. И сравнение с "кубик-рубиком" лишь путает. У кубик-рубика "картинки" связаны с осями вращения - поменяв одну картинку, поменяется группа других. А у вас непонятно, есть ли связи и какие - какие оси на какие картинки как влияют.
Мне эта задачка напоминает NP-полную задачу... Как-то было про изменение строки, даны n операций (например перестановка, циклический сдвиг и т.п.), найти самую короткую комбинацию операций. Но извиняюсь, уже не помню.
А так - брутфорсим нафик. 10 позиций, 10 символов, каждый символ может оказаться на любой позиции, символы не повторяются - максимум 10! вариантов, 3.628.800, каждый вариант представляем десятичным числом. (вместо 10 будем 0 использовать), 10.000.000.000 вариантов в 64-х битный лонг запихнём. Даже все варианты в память влезут. Вообще ерунда :)
Начинаем строить словарь с уже полученными значениями (чтобы не зациклиться) и дерево переходов.
Начинаем с 0123456789. Добавили словарь. Добавляем переход - крутим по циклу А - 8023456791. Смотрим, есть ли такое словаре? Нету. Сравниваем с ожидаемым - не, не совпало? Добавили в словарь, добавили новый узекл, добавили переход с маркировкой "А". Повторяем для Б, потом для С и Д. Сделали для всех операций? Есть узел не этом же уровне? Переходим к нему. Нет? Спускаемся на уровень ниже, если можем. Если новое число совпало с каким-то из словаря - "отменяем ход", рисуем "стоп, сюда не ходи". В общем поиск в ширину.
Это 100% можно сделать умнее, каждая трансмутация меняет цифры только в определённых позициях, но оно надо? меньше 4 миллионов вариантов отщёлкает ну... за 30 секунд? Так как мы в ширину ищем, то первый найденный путь и будет самым коротким.
А вот если будет 20 вариантов, то тут уже приплыли :) Придётся искать какой-нить 4/3 алгоритм.
меньше 4 миллионов вариантов отщёлкает ну... за 30 секунд?
Есть у меня некоторое сомнение, что блутфорсный алгоритм выдаст оптимальный результат.
Результат то нужно еще повторить ручками на "реальной модели". А если там будет шагов 50, допустим?
Да и наверняка математики, что то уже придумали для подобных случаев.
Возможно пойти по шагам.
Кнопки - вижу. Что они делают - непонятно.Грубо говоря у нас есть три круга, которые можно вращать. Два маленьких и один большой. Два маленьких вращаются только в одну сторону - две кнопки. А большой может вращаться по часовой стрелке и против - две кнопки.
Не совсем так. Вернее совсем не так. Тут надо искать точку в пространстве траекторий, где траектория имеет определенное начало, определенный конец, и минимальную длину. Для этого
1) кодируем как-то все точки на графе. Одно состояние фишек на досек - одно состоняие. Всего N узлов графа. Если N=10! то траекторий будет дофигища.
2) задаем сам граф в виде множетсва пар e=(исходное состоняие ∈ N, конечное состоняие ∈ N) - каждая такая пара (стрелка графа) соответствует одной из 4 операций. Можно например явно определить таблицу из 2 колонок с 4*N строк. Но в зависимости от алгоритма (или памяти мало) можно и функцию определить. С 4 стрелками из каждой точки число траекторий будет уже существенно меньше чем дофигища. Но все равно много.
3) Применяем
любимый алгоритм поиска кратчайшего пути на графе. Я помню только алгоритм Дейкстры но их существует туева хуча на все случаи жизни. В качестве параметров задаем начальное состоняние и желаемое конечное.
Вроде нашел как можно решать
https://habr.com/en/articles/322900/
Но это явно очень далеко от того что мне обычно требуется делать.
На графе чего?
Мы же не можем перемещать только одну точку забывая обо всех остальных.
Одна вершина графа - одно распределение чисел по доске.
Все вершины графа - все возможные распределения чисел по доске
Это множество определяется независимо от операций. Теоретически, могут быть состояния (вершины) которые будут недостижимы при некотором определении опеарций.
Можно как-то так реализовать рекурсивно поиск в ширину:
find_next_nodes(input_nodes) -> output_nodes
out_nodes = []
for in_node in input_nodes:
out1 = op1(node)
out2 = op2(node)
out3 = op3(node)
out4 = op4(node)
out_nodes.append([out1, out2, out3, out4])
return out_nodes // Все что достижимо из указанных узлов
while(not_found)
current_nodes = find_next_nodes(current_nodes)
if target_node in current_nodes
not_found = False
То же самое можно и на Прологе.
Функции операций знают как "вращать", т.е. двигать несколько фишек по достке одновременно. Например, из аргумента 0123456789 вернуть 9876543210
(это неправильно, но просто как пример входа и выхода такой функции).
upd:
- Вверху это не рекурсивный алгоритм, а просто цикл, но можно конечно рекурсивно без цикла
- Он не находут путь, а решает задачу достижимости. Для пути логика точно такая же, но вместо узлов надо хранить пути. Операции применяются к последнему узлу пути и возвращают более длинный путь
- Надо конечно проверять чтобы не попасть в уже пройденный узел. Например, хранить пройденные узлы а также избегать чтобы операция возвращала предыдущий узел (вращать в обратном направлении).
-
Это стандарный алгоритм поиска в ширину. Наверняка можно как-то оптимизировать, а иначе комп может загнуться
https://habr.com/en/articles/322900/
там довольно заумно, лучше ищите на слова simulated annealing в GSL есть такие решатели
OFF: Если бы у вас были бы дети, которые участвуют в BWINF, они бы вам быстренько решили - там организаторы помешаны на таких задачах
Примеры непонятностей- результат нажатия каждой кнопкирезультат нажатия каждой кнопки - поворот влево левого круга - поворот вправо правого круга - поворот вправо большого круга - поворот влево малого круга какого результата нужно достичь - если смотреть на картинку, там нарисованы животные на фоне. И такие же животные есть внутри кругов. Вот они и должны совпасть. Типа поставить все цвета на определенное для них место.
- какого результата нужно достичь
лучше ищите на слова simulated annealing
поискал, но не вижу ничего общего
https://www.baeldung.com/cs/simulated-annealing
1. This involves defining the energy function, i.e., the function to minimize or maximize
2. A perturbation function is defined to generate new candidate solutions. This function should generate solutions that are close to the current solution but not too similar
Какая может быть функция чтобы переместить одну единственную фишку, может еще и можно придумать.
А вот связать всё вместе...
не, это бибер - он очень простой, надо https://bwinf.de/bundeswettbewerb/
например, вторая не юниорская задача первого тура этого года. Раньше тоже было, там в архивах решения есть. Я просто знаю этого Вольфганга Поля лично, это тот, что эту олимпиаду огранизует, он на такого рода задачах просто помешан, а в этой бундеслиге за прошлые года есть все решения (не программы, а идеи).
например, вторая не юниорская задача первого тура этого года. https://bwinf.de/bundeswettbewerb/
Спасибо конечно, но что по данной ссылке я не вижу никакого списка задач Ну может завтра еще по всем ссылкам похожу.
Вот специально для тебя сделал, может так будет более понятно
назад
список