Метод ветвей и границ
Инициализировать
очередь
Очередь
пуста?
C
4
да
Конец
нет
S
Изъять путь из очереди
Путь ведет
к цели?
нет
Продлить путь;
Отсортировать очередь
Асирян
5
3
B
да
SAB:7
SBA:9
SBC:9
SABC:11
SADG:11
SBAD:12
SB:5
SAD:6
SBA:9
SBC:9
SABC:11
SADG:11
SBAD:12
SBCE:15
SAB:7
SBC:9
SADG:11
SBAD:12
SBCE:15
G
4
A
Очередь
SAD:6
SAB:7
SBA:9
SBC:9
SABC:11
SADG:11
S:0
SA:3
SB:5
E
6
3
5
D
0 S
3 A
5 B
7 B
6 D 9 A
9 C
11 C
11 G 12 D
15 E
1
МВГ + список
пройденных вершин
Инициализировать
очередь
Очередь
пуста?
C
4
да
Конец
нет
S
Изъять путь из очереди
Путь ведет
к цели?
нет
Продлить путь, если
еще не был продлен;
Отсортировать очередь
Асирян
5
3
B
да
SB:5
SAD:6
SAB:7
SBA:9
SBC:9
SADG:11
SBCE:15
SAB:7
SBA:9
SBC:9
SADG:11
SBC:9
SADG:11
G
4
A
Очередь
S:0
SA:3
SB:5
SAD:6
SAB:7
SBA:9
SBC:9
SADG:11
E
6
3
5
D
0 S
3 A
7 B
5 B
6 D 9 A
11 G
9 C
15 E
2
МВГ + допустимая
эвристика
Инициализировать
очередь
Очередь
пуста?
C
4
да
S
Изъять путь из очереди
нет
Продлить путь;
Отсортировать очередь
Асирян
5
Конец
нет
Путь ведет
к цели?
6
3
да
SAD:11
S:0
SA:10+
SB:11
SADG:11
SB:11
SAD:11
SAB:13
SAB:13
SBA:16+
SBC:16+
7+
6
B
G
7+
4
A
Очередь
E
3
D
5
0 S
10+ A
13 B
11 B
11 D 16+ A 16+ C
11 G
3