Какой алгоритм подойдет здесь? Обход серии взаимосвязанных узлов, охватывающих их все с минимальным повторением - PullRequest
Новая
       7

Какой алгоритм подойдет здесь? Обход серии взаимосвязанных узлов, охватывающих их все с минимальным повторением

3 голосов
/ 04 марта 2011

Я помогаю другу, пишу ему программу.Он перезаписывает саундтрек к старой игре Lucasarts Tie Fighter.В игре использовалась система iMuse - каждая «дорожка» состояла из нескольких небольших звуковых сигналов.Игра объединила их для создания динамического саундтрека, который изменился в зависимости от ситуации.

Для каждого «трека» существует набор правил, определяющих, какой сигнал перейти к следующему.В этом есть случайный элемент, например:

SUCC CUES
SUCC-01 перемещается в SUCC-02
SUCC-02 перемещается в SUCC-03 или SUCC-04
SUCC-03 перемещается в SUCC-01 или SUCC-04
SUCC-04 перемещается в SUCC-05
SUCC-05 перемещается в SUCC-01 или SUCC-06 или SUCC-08
SUCC-06 перемещается к SUCC-04 или SUCC-07
SUCC-07 перемещается к SUCC-01 или SUCC-02 или SUCC-04 или SUCC-08
SUCC-08 перемещается к SUCC-02 или SUCC-06
SUCC-IN переходит к SUCC-01

Есть много других треков, подобных этому, с большим количеством подсказок.По сути, каждая дорожка представляет собой сетку взаимосвязанных узлов.Он хочет, чтобы программа анализировала сигналы и создавала списки воспроизведения для каждой дорожки, которые удовлетворяют 2 критериям:

  • Используются все сигналы в дорожке
  • Существует минимальное повторение сигналов

У меня минимальный опыт работы с алгоритмами, поэтому я не уверен, какой алгоритм подойдет для этой проблемы.Прочитать мое предположение было бы своего рода коммивояжером.

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

1 Ответ

1 голос
/ 04 марта 2011

Я бы посоветовал вам попробовать простое эвристическое решение, основанное на грубой силе, основанное на поиске по первому дыханию:

На каждом уровне поиска сигналы «априори», которые не являются частью текущего решения,Подсчитайте уникальное количество сигналов в вашем решении (это может быть сложно, но это не так сложно: просто запомните цепочку сигналов, из которой вы пришли (от начала до текущего сигнала), и у вас есть вся необходимая информация) и завершитекак только вы найдете решение, использующее все сигналы (оно должно быть минимально минимальным).

Этот «алгоритм» далек от совершенства или производительности, но если у вас нет трека, построенного из нескольких тысячcues, это не должно быть проблемой.

Обратите внимание, что этот «алгоритм» будет пойман в бесконечный цикл, если ваш список треков содержит сигналы, которые недоступны из вашего начального сигнала.Используйте счетчик для завершения, например, если ваш результат поиска более чем в десять раз превышает число подсказок, или что-то в этом роде.

У меня нет кода delphi, но его не должно быть трудно найти для дыхания.Первый поиск.

...