Используйте A * на графике возможных ходов с функцией heuristi c: количество ведер, отличающихся от их целевого ведра, делится на два. То есть b/2, где b - количество сегментов, в которых содержится неправильное количество.
A * часто рассматривается как алгоритм поиска пути для подобных единиц маршрутизации в игре, но он работает на любом графике, где вы можете найти heuristi c, который никогда не переоценивает расстояние до целевого узла. Самое главное, что A *, вооруженный таким heuristi c, всегда найдет кратчайший путь. Исходя из теории игр, мы можем представить граф, узлы, соединенные ссылками, где каждый узел представляет собой возможное распределение шаров между корзинами, а каждая ссылка представляет собой законный ход, который может сделать машина. Ваш начальный узел - это начальное распределение шаров. Ваш целевой узел - это целевое распределение шаров.
С помощью этого графика мы могли бы применить поиск по первому дыханию и подождать, пока нам не случится посетить целевой узел. Это дало бы нам кратчайший набор шагов от начального распределения к целевому, поскольку это поиск с первого дыхания. (Это более или менее эквивалентно алгоритму Дейкстры в этом случае, потому что каждый ход имеет одинаковую стоимость (длину) в 1 ход)
Однако мы можем добиться большего. A * просматривает график, используя heuristi c. В частности, это похоже на поиск по первому дыханию, за исключением того, что вместо следующего посещения не посещенного узла, ближайшего к начальному узлу, A * затем посещает не посещенный узел, который минимизирует g(n) + h(n), где g(n) - это длина от непосещенного узел, n, до начального узла, а h(n) - это эвристия c для расстояния от невидимого узла, n, до цели. Это означает, что мы тратим меньше вычислительного времени на поиск оптимального пути, уходя от цели, когда сначала проверяем очевидный путь к цели. Математически доказано, что A * даст вам оптимальный путь от вашего начального узла до целевого узла, если вы найдете допустимый heuristi c, то есть heuristi c, который никогда не переоценивает расстояние до цели. Например, в видеоигре длина пройденного пути между двумя точками всегда больше или равна расстоянию до вороны. Несмотря на то, что наш граф не является графом, представляющим физическое пространство, мы все же можем найти допустимую heuristi c.
Ход может в лучшем случае заставить 2 ведра иметь правильное количество шаров, поскольку ход может Влияет только на два ведра. Таким образом, например, если мы посчитаем наши ведра и увидим, что в 4 ведрах содержится неправильная информация о шариках, то мы знаем, что потребуется как минимум 2 хода. Вполне возможно больше, но оно не может быть меньше 2.
Позволяет сделать наш heuristi c «количеством ведер с неправильным количеством шаров, разделенных на 2».
Наш heuristi c не переоценивает количество ходов, необходимых для получения желаемого количества шаров, так как даже самый лучший вид хода, в котором вы подходите для счастливых пар, может произойти за каждый ход, который вы только t ie наш heuristi c. Наш heuristi c недооценивает ходы довольно часто, но это нормально, вычисления займут больше времени, но не дадут неправильного результата, а план результата для ходов будет по-прежнему кратчайшим. Таким образом, наша heuristi c является допустимой, что означает, что она никогда не переоценивает количество ходов.
Следовательно, A * с heuristi c из "числа ведер, у которых неправильное количество шариков разделено на 2 "всегда найдет наименьшее число ходов, чтобы достичь распределения.
Возможно, можно найти лучшую эвристию c, если так, то поиск будет go быстрее. Это был просто первый heuristi c, о котором я думал.