Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

графе;

*

печать

информации

о

наилучшем

пути

от start

до

finish.

Используется

в

программном

проекте

для

решения

транспорт­

ной

задачи

(задачи

коммивояжера).

|

'^/Давыдов

В.Г,

Консольное

приложение^

Visual

C++

6

I

//

Включаемый

файл

программного

проекта

для

решения

транс­

портной

задачи

(задачи

коммивояжера)

#include

"GrHead.h"

//

Определения

объектов

с

описателем

класса

хранения

внешний.

//

Их

объявление

имеется

в

заголовочном

файле

проекта

и

//

доступно

в

других

файлах

проекта

Inb

start;

//

Вершина

-

старт

пути

//

Эти

объекты

определяем

в

данном

месте^

чтобы

при

//

взаимнорекурсивных

вызовах

функций

PassWay(

)

и

//

ForStep

(

)

они

не

создавались

заново

GRAPH

Or;

//

Граф

W

*pMinWay;

//

Указатель

на

массив

структур

с

//

информацией

о

наилучшем

пути

из

Int

//

вершины

start

в

finish

finish,

//

Вершина

-

финиш

пути

one,

//

1-я

вершина

текущей

дуги

two/

//

2-я

вершина

текущей

дуги

//

Шаг

вперед

по

ребру

с

индексом

IndArc

из

вершины

topi

в

//

вершину

top2

void. ForStep

(

±пЬ

topi,

//

Достигнутая

вершина,

из

которой

int

//

шагаем

вперед

IndArc,

//

Индекс

ребра,

по

которому

int

//

делается

шаг

вперед

top2

)

//

Вершина

на

конце

ребра

{

£2.аа.Ь

NewDist;

//

Расстояние

до

top2

по

пути

через

//

topi

NewDist

= pMinWayl

topi

] . SumDist

+

Or.pArc[

IndArc

].weight;

±f(

!pMinWay[

top2

].

exist

)

{

//

Пока

пути

до

top2

нет

pMinWayl

top2

].exist

=

1;

pMinWay[

top2

]. SumDist

=

NewDist/

pMinWayf

top2

J.ref

= topi/

PassWay (

top2

)

/

}

else

{

//

Путь

до

top2

уже

существует

if(

pMinWay[

top2

].

SumDist

>

NewDist

)

{

//

Новый

путь

короче

pMinWayl

top2

].SumDist

=

NewDist/

280

pMinWayl

top2

J.ref

=

topi;

PassWay(

top2

) ;

}

}

return/

}

//

Прохождение

пути

от достигнутой

вершины

InterMedlate,

если

//

он

есть г до вершины

finish

void. PassWay

(

вершина -

отправная

точка пути

//

Достигнутая

Int

InterMedlate

)

{

±nt

к;

//

Индекс

текущей

дуги

графа

±f(

InterMedlate

== finish

)

{

return/

//

! ! !

Выход

из

рекурсии

}

else

{

// Перебор

ребер

графа

£ог(

к

==

О/ к

< Gr.NumArc/

к++ )

{

one

=

Gr.pArc[

к

].

first/

two

=

Gr.pArc[

к

J.last/

шага

по

ребру

и

//

Определения

направления

//

выполнение

шага

в

найденном

направлении

±f(

one

==

InterMedlate

)

{

ForStep(

one

г к,

two

)

/

}

else

±f(

two

==

InterMedlate

)

(

ForStep

(

two,

k,

one

)

;

}

}

return/

//

!!!

Альтернативный

вариант

выхода

//

из

рекурсии

}}

//	Поиск пути		минимального			веса	в	неориентированном
//	взвешенном				графе
void, solution			(	void )
{	int			j /	//	Индекс		вершины
	//	Начальная			подготовка	массива		структур с информацией	о
	//	наилучшем			пути		j++	)
	fori	j =	О/	j	< Gr.NumTop/

{

281

*pFileOut, // Указатель на файл вывода

*pMode ) // Указатель на режим вывода в файл

pMinWayf j		], exist	=	0;
}
pMinWay [	start	]. exist	= 1;
pMinWay[	start	] . SumDist = O.Of;
pMinWay[	start	J.ref	= -1;
// Рекурсивное		определение		требуемого пути
PassWay(	start	);

return/

}

// Печать информации о наилучшем пути от start до finish void. OutRes (

char char

{

FILE	*pStrOut;	//	Указатель на		структуру	со
±пЬ		//		сведениями	о файле	результатов
	TempTopf	//	Текуш,ая вершина пути
	RetCodel;	//		Возвраш;аемое значение		fclose ( )

//Открытие файла вывода

pStrOut	= fopen(		pFileOut^	pMode	);
±f( pStrOut		== NULL )
{
printf(		"\n	Ошибка 140. Файл %s для вывода не "
		"открыт \л",		pFileOut	);
exit	(	140 ) ;
)

//Печать информации о найденном пути

±f( !pMinWay[ fini'Sh ],exist )

{		(
printf
"\n	Искомого			пути не	существует \п" ) ;
}
else
{
// Печать оптимального					пути
ТетрТор =			finish/
fprintf(		pStrOut,
"\п	Вершина-финиш: %d, вершина - старт: %d "
"\л	Значение			минимального пути: %д \л",			finish,
		start,		pMinWay[ finish		].SumDist	)/
fprintf		( pStrOut, "\n			Список вершин, образуюш:их"
while		"	этот путь		(от finish	до start):	\п" )/
	( ТетрТор != -1 )

{

fprintf( pStrOut, " %4d ", ТетрТор )/ Temp Top = pMi nWay [ Temp Top ] . ref/

}

}

282

// Закрытие			файла		результатов
RetCodel		= fclose(			pStrOut	) ;
±f(	RetCodel		== EOF )
{	printf(		"\n	Ошибка 150.		Файл %s не закрыт	\n",
			pFileOut		) ;
	exit	( 150 )		;
}
//	Освобождение			динамической		памяти
GrFreeDM(		)	;

retujcn/

При файле исходных данных

56

О1 80

03 10

12 20

14 10

23 20

34 10

О1

получаем решение транспортной задачи в файле результатов в следующем виде:

Число вершин графа: 5 , число ребер: 6

Индекс ребра	1-я вершина	2-я вершина	Вес	ребра
0	О	1	80.	,000000
1	О	3	10.	,000000
2	1	2	20.	,000000
3	1	4	10.	,000000
4	2	3	20.	,000000
5	3	4	10.	,000000

	Верши на - финиш:		1, в ерши на - старт: О
	Значение минимального			пути: 30
Список	вершин,	образуюш;их	этот	путь (от finish	до start) :
1 , 4	3	О

Спецификация функции прохождения пути от достигнутой вершины до finish, если он есть, представлена на рис. 88.

283

Достигнутая вершина - отправная точка
пути	int InterMediate
	PassWay
Финиш пути	int finish
Граф	GRAPH Gr
input	process	output

Рис. 88. Спецификация функции прохождения пути от достигнутой вершины j\o finish

Необходимо обратить внимание, что в список параметров этой функции включен только один параметр - InterMediate- так как Gr, finish определены на внешнем уровне (повторяем, что для рекурсив­ ных функций число параметров нуэюно минимизировать). Текст функции PassWay приведен выше. На данном этапе рекомендуем рассмотреть только функцию PassWay. Остальные функции будут рассмотрены позже. Данная функция, как и функция ForStep, явля­ ется вспомогательной и вызывается из функции solution.

Из приведенной программы следует, что взаимно-рекурсивный вызов функций выглядит следующим образом (рис. 89).

PassWay( start);

Выход (InterMediate == finish или обработаны все ребра графа) Рис. 89. Взаимно-рекурсивный вызов функций Pass Way-ForStep

	Спецификация	функции solution	для решения задачи в целом
представлена на рис. 90.
Вершина - старт
пути	int start	solution	Массив с информацией о
Граф	GRAPH Gr		- • наилучшем пути
			W *pMinWay
	input	process	output
	Рис. 90. Решение задачи в целом

Список параметров этой функции пуст. Объясняется это тем.

284

что start, Gr, pMinWay являются глобальными объектами (определены на внешнем уровне). Текст программы, включающий определение функции solution, приведен выше. Данная функция, в отличие от предыдущих функций Pass Way и ForStep, является ин­ терфейсной функцией и вызывается для решения транспортной за­ дачи.

16.6. Пример поиска минимального пути в графе

Схема графа приведена на рис. 91.

	first	last	weight
0	0	1	80.0
1	0	3	10.0
2	1	2	20.0
3	1	4	10.0
4	2	3	20.0
5	3	4	10.0

Внимание! Нумерация вершин и ребер начинается с нуля, так как минимальный индекс элемента массива с языках Си/С++ равен нулю.

Рис. 91. Пример схемы графа

Состояние массиваpMinWay после подготовки в функции solu­ tion перед вызовом функции PassWay{ start ) показано на рис. 92.

	1 1					Индексы вершин
		0	0	0	0	exist
pMinWay	0.0	0.0	0.0	0.0	0.0	SumDist
	-1	0	0	0	0	ref (REFerence - ссылка):
	start	finish				-1 означает конец списка
Рис. 92. Состояние массива,pMinWay						после начальной подготовки

В качестве задания для самостоятельной работы предлагается проанализировать работу программы и убедиться, что в результате в массиве pMin Way получится информация, показанная на рис. 93.

Важное замечание! В данном частном случае массивpMinWay указывает наилучшие пути от start до всех остальных вершин. Но в общем случае это не гарантируется. Гарантируется лишь оптималь-

285

ность пути из start		ъ finish.
		1	1	1		Индексы вершин
	1				1	exist
pMJnWay	0.0	30.0	30.0	10.0	20.0	SumDist
	-1	4	3	0	3	ref (REFerence - ссылка):
	start	finish				-1 означает конец списка

i'

Рис. 93. Состояние массива/?МшЖду после решения транспортной задачи

16.7.Печать информации о наилучшем пути

врассмотренном примере получена информация о наилучшем

пути между вершинами start \\ finish в обратном порядке (рис. 94).

Рис. 94. Информация о наилучшем пути между вершинами start и finish

Прототип и определение функции OutRes^ в которой произво­ дится печать информации о найденном оптимальном пути, приведе­ ны в подразд. 16.5.2. Там же приведен текст функции, выполняющей тестирование спроектированного класса, и результаты тестирования.

Советуем внимательно изучить этот пример и поэксперимен­ тировать с ним.

При этом рекомендуем обратить внимание на следуюш^ие осо­ бенности рассмотренного программного проекта:

1. Взаимно-рекурсивный вызов функций Pass fVay-ForStep (ва­ рианты завершения рекурсии в методе Pass Way; минимизация коли­ чество параметров и внутренних данных в этих методах; алгоритми­ ческое решение, обеспечивающее получение решения транспортной задачи при неполном переборе путей между заданными вершинами).

2.Структуру спроектированной программы.

3.Оформление исходных текстов

286

4.Терминологию при работе с графами.

5.Практическую значимость решения транспортной задачи (получение оптимального пути между городами, связанными раз­ ветвленной системой дорог; определение оптимального маршрута между заданными пунктами в крупном городе и т.п.).

17. поиск

Поиск, как и сортировка, может быть двух видов.

1. Внутренний поиск - поиск в оперативной памяти, в таблице (т.е. в массиве).

2. Внегиний поиск- поиск на внешней памяти (на магнитном диске или магнитной ленте).

Рассмотрим широко распространенные задачи внутреннего поиска.

17.1. Постановка задачи внутреннего поиска

Таблица данных располагается в оперативной памяти и содер­ жит некоторое количество строк, вид которых представлен на рис. 95.

8 байт	62 байта (LDATA-1), данное - другие сведения
(LKEY-1,
LengthKEY).
ключ для
поиска	Рис. 95. Структура строки таблицы

Строка таблицы может занимать, например, 70 байт памяти (см. рис. 95). Байт хранит код некоторого символа.

Приведем несколько примеров таблиц такого рода.

1. Русско-английский словарь. Ключ - русское слово, данное - соответствующее английское слово и другие сведения.

2.Англо-русский словарь. Аналогично.

3.Таблица домашних адресов: ключ - фамилия, другие сведе­ ния - домашний адрес и телефон.

Для дальнейшего примем допущение, что ключ поиска может содержать только строчные буквы латинского алфавита, цифры и символ пробела, начинается с буквы, а символ пробела (символы пробелов) может (могут) быть только завершающим (завершающи­ ми).

В кодовых таблицах буквы латинского алфавита упорядочены, заглавные (прописные) буквы предшествуют строчным, цифры предшествуют заглавным буквам, а пробел - цифрам (в смысле ал-

288

фавита). Русские буквы в кодовых таблицах - в общем случае неупорядочены. Отсюда вывод - сравнение ключей поиска, содержащих латинские буквы, можно проводить непосредственно (например, с помощью строковой функции strcmp, как в нашем случае). И наобо­ рот, если ключ содержит русские буквы, то для сравнения ключей следует использовать специально написанную для этой цели функ­ цию.

Данные для поиска в таблице могут иметь следующий вид:

const	±nt	LKEY	= 9;	/ /	Длина	ключа в строке таблицы
// Длина данного		в	строке	//	LKEY~1
				таблицы		LDATA-1
const	xnt	LDATA = 63;

//Тип для строки таблицы

struct STRTAB

(

//Ключ

char кеу[ LKEY ];

//Данные

} ;	сЬаг		data[	LDATA		];
//	приведенные		ниже	объекты		будут	использованы		практически		во
//	веек функциях			поиска в		таблице	и их		целесообразно
//	определить		с описателем			класса	хранения		внешний	- это
//	сделает	указанные			объекты доступными			в	других	файлах
//	проекта	и	всех		функциях		первой	строки таблицы			в
STRTAB			*рТаЫе;		//	Адрес
±nt			size;		//	динамической			памяти
					//	Размер	таблицы

Спецификация функции, выполняющей поиск в таблице, пред­ ставлена на рис. 96. Из нее следует, что хотя общее число исходных данных {input) и результатов, получаемых из функции поиска {out­ put), равно пяти, все же в список параметров функции следует включить только три из них, так как два исходных данных - table и size — следует определить на внешнем уровне как глобальные объек­ ты.

STRTAB *рТаЬ1е		И	•	Int	&found
int	size	м search
char	KeyWord[LKEY]	И	•	int	&line
	input	process		output

Рис. 96. Спецификация функции поиска в таблице

Решение задачи поиска заключается в том, что в таблице рТаЫе надо найти строку с полем ключа, совпадающим со словом

289