Deutsch
Germany.ruФорумы → Архив Досок→ Программирование

Как решать подобные задачи?

2077  1 2 3 все
MrSanders коренной житель09.01.24 14:02
NEW 09.01.24 14:02 
в ответ AlexNek 07.01.24 21:00

Мне эта задачка напоминает NP-полную задачу... Как-то было про изменение строки, даны n операций (например перестановка, циклический сдвиг и т.п.), найти самую короткую комбинацию операций. Но извиняюсь, уже не помню.

А так - брутфорсим нафик. 10 позиций, 10 символов, каждый символ может оказаться на любой позиции, символы не повторяются - максимум 10! вариантов, 3.628.800, каждый вариант представляем десятичным числом. (вместо 10 будем 0 использовать), 10.000.000.000 вариантов в 64-х битный лонг запихнём. Даже все варианты в память влезут. Вообще ерунда :)

Начинаем строить словарь с уже полученными значениями (чтобы не зациклиться) и дерево переходов.

Начинаем с 0123456789. Добавили словарь. Добавляем переход - крутим по циклу А - 8023456791. Смотрим, есть ли такое словаре? Нету. Сравниваем с ожидаемым - не, не совпало? Добавили в словарь, добавили новый узекл, добавили переход с маркировкой "А". Повторяем для Б, потом для С и Д. Сделали для всех операций? Есть узел не этом же уровне? Переходим к нему. Нет? Спускаемся на уровень ниже, если можем. Если новое число совпало с каким-то из словаря - "отменяем ход", рисуем "стоп, сюда не ходи". В общем поиск в ширину.


Это 100% можно сделать умнее, каждая трансмутация меняет цифры только в определённых позициях, но оно надо? меньше 4 миллионов вариантов отщёлкает ну... за 30 секунд? Так как мы в ширину ищем, то первый найденный путь и будет самым коротким.

А вот если будет 20 вариантов, то тут уже приплыли :) Придётся искать какой-нить 4/3 алгоритм.

#21 
Murr патриот09.01.24 16:26
Murr
NEW 09.01.24 16:26 
в ответ AlexNek 09.01.24 00:03

Кнопки - вижу.

Что они делают - непонятно.


Ну ладно - те что по центру , видимо, поворачивают на... 1, 2, 3... 5... 100 секторов

А как вторая пара должна фунциклировать?

#22 
AlexNek патриот09.01.24 17:51
AlexNek
NEW 09.01.24 17:51 
в ответ MrSanders 09.01.24 14:02
меньше 4 миллионов вариантов отщёлкает ну... за 30 секунд?

Есть у меня некоторое сомнение, что блутфорсный алгоритм выдаст оптимальный результат.

Результат то нужно еще повторить ручками на "реальной модели". А если там будет шагов 50, допустим?

Да и наверняка математики, что то уже придумали для подобных случаев.


Возможно пойти по шагам.

https://habr.com/en/companies/ruvds/articles/529780/

#23 
AlexNek патриот09.01.24 17:54
AlexNek
NEW 09.01.24 17:54 
в ответ Murr 09.01.24 16:26
Кнопки - вижу. Что они делают - непонятно.
Грубо говоря у нас есть три круга, которые можно вращать. Два маленьких и один большой. Два маленьких вращаются только в одну сторону - две кнопки. А большой может вращаться по часовой стрелке и против - две кнопки.
#24 
Бесконечный цикл постоялец09.01.24 19:08
NEW 09.01.24 19:08 
в ответ MrSanders 09.01.24 14:02, Последний раз изменено 09.01.24 19:11 (Бесконечный цикл)

Не совсем так. Вернее совсем не так. Тут надо искать точку в пространстве траекторий, где траектория имеет определенное начало, определенный конец, и минимальную длину. Для этого

1) кодируем как-то все точки на графе. Одно состояние фишек на досек - одно состоняие. Всего N узлов графа. Если N=10! то траекторий будет дофигища.

2) задаем сам граф в виде множетсва пар e=(исходное состоняие ∈ N, конечное состоняие ∈ N) - каждая такая пара (стрелка графа) соответствует одной из 4 операций. Можно например явно определить таблицу из 2 колонок с 4*N строк. Но в зависимости от алгоритма (или памяти мало) можно и функцию определить. С 4 стрелками из каждой точки число траекторий будет уже существенно меньше чем дофигища. Но все равно много.

3) Применяем любимый алгоритм поиска кратчайшего пути на графе. Я помню только алгоритм Дейкстры но их существует туева хуча на все случаи жизни. В качестве параметров задаем начальное состоняние и желаемое конечное.


#25 
AlexNek патриот09.01.24 19:25
AlexNek
NEW 09.01.24 19:25 
в ответ AlexNek 09.01.24 17:54

Вроде нашел как можно решать

https://habr.com/en/articles/322900/

Но это явно очень далеко от того что мне обычно требуется делать.

#26 
AlexNek патриот09.01.24 19:34
AlexNek
NEW 09.01.24 19:34 
в ответ Бесконечный цикл 09.01.24 19:08
Применяем любимый алгоритм поиска кратчайшего пути на графе

На графе чего?

Мы же не можем перемещать только одну точку забывая обо всех остальных.

#27 
Бесконечный цикл постоялец09.01.24 19:57
NEW 09.01.24 19:57 
в ответ AlexNek 09.01.24 19:34, Последний раз изменено 09.01.24 21:05 (Бесконечный цикл)
На графе чего?
Мы же не можем перемещать только одну точку забывая обо всех остальных.

Одна вершина графа - одно распределение чисел по доске.

Все вершины графа - все возможные распределения чисел по доске

Это множество определяется независимо от операций. Теоретически, могут быть состояния (вершины) которые будут недостижимы при некотором определении опеарций.


Можно как-то так реализовать рекурсивно поиск в ширину:


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 // Все что достижимо из указанных узлов


current_nodes = [start_node]


while(not_found)

current_nodes = find_next_nodes(current_nodes)

if target_node in current_nodes

not_found = False


То же самое можно и на Прологе.


Функции операций знают как "вращать", т.е. двигать несколько фишек по достке одновременно. Например, из аргумента 0123456789 вернуть 9876543210

(это неправильно, но просто как пример входа и выхода такой функции).


upd:

- Вверху это не рекурсивный алгоритм, а просто цикл, но можно конечно рекурсивно без цикла

- Он не находут путь, а решает задачу достижимости. Для пути логика точно такая же, но вместо узлов надо хранить пути. Операции применяются к последнему узлу пути и возвращают более длинный путь

- Надо конечно проверять чтобы не попасть в уже пройденный узел. Например, хранить пройденные узлы а также избегать чтобы операция возвращала предыдущий узел (вращать в обратном направлении).

- Это стандарный алгоритм поиска в ширину. Наверняка можно как-то оптимизировать, а иначе комп может загнуться

#28 
AlexNek патриот09.01.24 21:41
AlexNek
NEW 09.01.24 21:41 
в ответ Бесконечный цикл 09.01.24 19:57
Все вершины графа - все возможные распределения чисел по доске

но у графа есть еще и ребра. То есть вначале как то строим монстрика, а после ищем самый короткий путь?

Да, должно вроде работать.

#29 
MrSanders коренной житель10.01.24 07:55
NEW 10.01.24 07:55 
в ответ AlexNek 09.01.24 21:41

Угу. А теперь сравниваем с моим предложением, где решение находится в процессе построения монстра (с высокой вероятностью что нам не придётся строить его до конца).

#30 
Murr патриот10.01.24 07:56
Murr
NEW 10.01.24 07:56 
в ответ AlexNek 09.01.24 17:54

есть три круга

-----

ну да - рацию надо установить на броневичке.


Еще раз - постановка задачи все еще не понятна.

Примеры непонятностей

- результат нажатия каждой кнопки

- какого результата нужно достичь

#31 
Murr патриот10.01.24 08:00
Murr
NEW 10.01.24 08:00 
в ответ AlexNek 09.01.24 19:34

На графе чего?

-----

Там один граф!

И это ни графина, ни графини - нету.

#32 
Murr патриот10.01.24 08:04
Murr
10.01.24 08:04 
в ответ Бесконечный цикл 09.01.24 19:57

upd:

-----

Вполне достаточно сказать - альфа-алгоритм (перебор с возвратом)

#33 
wasja-de постоялец10.01.24 09:42
NEW 10.01.24 09:42 
в ответ AlexNek 09.01.24 19:25
https://habr.com/en/articles/322900/

там довольно заумно, лучше ищите на слова simulated annealing в GSL есть такие решатели


OFF: Если бы у вас были бы дети, которые участвуют в BWINF, они бы вам быстренько решили - там организаторы помешаны на таких задачах

#34 
AlexNek патриот10.01.24 17:49
AlexNek
NEW 10.01.24 17:49 
в ответ MrSanders 10.01.24 07:55
А теперь сравниваем с моим предложением

Сорри, не могу. Не доходит пока принцип работы смущ

Да и оба решения - не та информация которую было интересно узнать.

#35 
AlexNek патриот10.01.24 17:55
AlexNek
NEW 10.01.24 17:55 
в ответ Murr 10.01.24 07:56
Примеры непонятностей- результат нажатия каждой кнопки
- какого результата нужно достичь
результат нажатия каждой кнопки - поворот влево левого круга - поворот вправо правого круга - поворот вправо большого круга - поворот влево малого круга какого результата нужно достичь - если смотреть на картинку, там нарисованы животные на фоне. И такие же животные есть внутри кругов. Вот они и должны совпасть. Типа поставить все цвета на определенное для них место.
#36 
AlexNek патриот10.01.24 18:04
AlexNek
NEW 10.01.24 18:04 
в ответ wasja-de 10.01.24 09:42
лучше ищите на слова 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

Какая может быть функция чтобы переместить одну единственную фишку, может еще и можно придумать.

А вот связать всё вместе...


#37 
wasja-de постоялец10.01.24 18:52
NEW 10.01.24 18:52 
в ответ AlexNek 10.01.24 18:04

поищите на bwinf.de похожую (в этом году была точно, в прошлом - не уверен, но до точно были не раз) там есть решения за прошлые годы.

#38 
AlexNek патриот10.01.24 19:09
AlexNek
NEW 10.01.24 19:09 
в ответ wasja-de 10.01.24 18:52

тут? пока не нашел

https://bwinf.de/biber/archiv/aufgabensammlung/

#39 
wasja-de постоялец11.01.24 20:18
NEW 11.01.24 20:18 
в ответ AlexNek 10.01.24 19:09

не, это бибер - он очень простой, надо https://bwinf.de/bundeswettbewerb/

например, вторая не юниорская задача первого тура этого года. Раньше тоже было, там в архивах решения есть. Я просто знаю этого Вольфганга Поля лично, это тот, что эту олимпиаду огранизует, он на такого рода задачах просто помешан, а в этой бундеслиге за прошлые года есть все решения (не программы, а идеи).

#40 
1 2 3 все