Это не домашнее задание, чисто для моего побочного проекта.
Я реализую оператор кроссовера перестановки для генетического алгоритма (решение коммивояжера, где каждое число представляет индекс города), и у меня возникла проблема с граничным случаем, когда нет сопоставления 1 к 1.
Рассмотрим два генома ниже и предположим, что последние две записи поменяны местами. Таким образом, 5 отображается в 6, а 6 отображается в 7. Итак, что происходит, когда я нажимаю номер 6 - следует ли мне изменить его на 5 или 7, и это может привести к недействительному туру, когда город посещают дважды.
//initial case
GenomeA: [ 2, 3, 1, 4, 0, 7, 5, 6 ]
GenomeB: [ 1, 2, 0, 3, 4, 5, 6, 7 ]
5 <--> 6
6 <--> 7
//after mapping
GenomeA: [ 2, 3, 1, 4, 0, 6, 6, 7 ]
GenomeB: [ 1, 2, 0, 3, 4, 6, 5, 6 ]
Следует ли мне случайным образом выбрать другой номер, если номер уже сопоставлен? Или мне не следует переключать какие-либо номера, которые уже были сопоставлены?
Например,
a) Evaluate first set of numbers (5 <--> 6)
b) Since 5 has not been mapped, map 5 to 6 and vice versa
c) Evaluate second set of numbers (6 <--> 7)
d) Since 6 is already mapped to 7, ignore this set of numbers
