Алгоритм нахождения ортогонального пути между двумя 10-значными числами

Question

Пусть S будет набором из 10 цифр.Учитывая любые два числа v и w в S , я хотел бы знать, существует ли последовательность чисел v = u_0, u_1,..., u_k = w так, что:

1. каждый u_i находится в S
2. для каждого i = 1, .., k , числа u_ {i-1} и u_i отличаются ровно на одну позицию

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

В идеале, я бы предпочел решение C (или псевдокод), но я действительно, действительно ценим любые и все предложения по этому вопросу!Спасибо!

Answer 1

Формируйте график из элементов S: u и v смежны, если они отличаются ровно одной координатой.

Теперь, учитывая, что u, сначала выполните поиск в ширину, пока не нажмете v.

Answer 2

Я бы преобразовал S в граф объектов узлов, где каждый объект узла содержит ссылки на соседние узлы. (В некоторых языках программирования читайте «ссылки» как «указатели».) Смежность определяется вашим условием 2 в последовательности, так что любой путь через результирующий граф является последовательностью, соответствующей двум условиям.

Оттуда, это простая задача проверки связности двух вершин в вашем графе. Самое простое решение - поиск в ширину . (Этот конкретный алгоритм также может найти кратчайший путь (и).)