"A*算法：静态路网中最有效短路径搜索" 资源-CSDN下载

需积分: 30 54 浏览量 2019-04-22 10:19:32 上传评论 2 收藏 2.34MB PDF 举报

资源推荐

资源详情

资源评论

IEEE

TRANSACTIONS

OF

SYSTEMS

SCIENCE

AND

CYBERNETICS,

VOL.

ssc-4,

NO.

2,

JULY

1968

[N1

J.

E.

Falk,

"Lagrange

multipliers

and

nonlinear

programming,"

J.

Math.

Anal.

Appl.,

vol.

19,

July

1967.

[6]

0.

L.

Mangasarian

and

J.

Ponstein,

"Minimax

and

duality

in

nonlinear

programming,"

J.

Math.

Anal.

Appl.,

vol.

11,

pp.

504-

518,

1965.

[7]

J.

Stoer,

"Duality

in

nonlinear

programming

and

the

minimax

theorem,"

Numerische

Mat

hematik,

vol.

5,

pp.

371-379,

1963.

[8]

R.

T.

Rockafellar,

"Duality

and

stability

in

extremum

prob-

lems

involving

convex

functions,"

Pacific

J.

Math.,

vol.

21,

pp.

167-187,

1967.

[9]

P.

Wolfe,

"A

duality

theorem

for

nonlinear

programming,"

Q.

A

ppl.

Math.,

vol.

19,

pp.

239-244,

1961.

[10]

R.

T.

Rockafellar,

"Nonlinear

programming,"

presented

at

the

American

Mathematical

Society

Summer

Seminar

on

the

Math-

ematics

of

the

Decision

Sciences,

Stanford

University,

Stanford,

Calif.,

July

August

1967.

[1ll

D.

G.

Luenberger,

"Convex

programming

and

duLality

in

normal

space,"

Proc.

IEEE

Systems

Science

and

Cybernetics

Conf.

(Boston,

Mass.,

October

11-13,

1967).

[12]

J.

M.

Danskin,

"The

theory

of

max-min

with

applications,"

J.

SIAM,

vol.

14,

pp.

641-665,

July

1966.

113]

W.

Fenchel,

"Convex

cones,

sets,

and

functions,"

mimeo-

graphed

notes,

Princeton

University,

Princeton,

N.

J.,

September

1963.

[14]

R.

Fletcher

and

M.

J.

D.

Powell,

"A

rapidly

convergent

descent

method

for

minimization,"

Computer

J.,

vol.

6,

p.

163,

July

1963.

[115

L.

S.

Lasdon

and

A.

D.

Waren,

"Mathematical

programming

for

optimal

design,"

Electro-Technol.,

pp.

53-71,

November

1967.

[16]

J.

B.

Rosen,

"The

gradient

projection

method

for

nonlinear

programming,

pt.

I,

linear

constraints,"

J.

SIAM,

vol.

8,

pp.

181-

217,

1960.

[17]

R.

Fletcher

and

C.

M.

Reeves,

"Function

minimization

by

conjugate

gradients,"

Computer

J.,

vol.

7,

July

1964.

[I8]

D.

Goldfarb,

"A

conjugate

gradient

method

for

nonlinear

programming,"

Ph.D.

dissertation,

Dept.

of

Chem.

Engrg.,

Prince-

ton

University,

Princeton,

N.

J.,

1966.

[19]

L.

S.

Lasdon,

"A

multi-level

technique

for

optimization,"

Ph.D.

dissertation,

Systems

Research

Center,

Case

Institute

of

Technology,

Cleveland,

Ohio,

Rept.

SRC

50-C-64-19,

1964.

120]

L.

S.

Lasdon

and

J.

D.

Schoeffler,

"A

multi-level

technique

for

optimization,"

Preprints,

Joint

Automatic

Control

Conf.,

Troy,

N.

Y.,

June

22-25,

1965,

pp.

85-92.

[21]

'-,"Decentralized

plant

control,"

ISA

Trans.,

vol.

5,

pp.

175-183,

April

1966.

[22]

C.

B.

Brosilow

and

L.

S.

Lasdon,

"A

two

level

optimization

technique

for

recycle

processes,"

1965

Proc.

AICHE-Symp.

on

Application

of

Mathematical

Models

in

Chemical

Engineering

Re-

search,

Design,

and

Production

(London,

England).

[21]

L.

S.

Lasdon,

"Duality

and

decomposition

in

mathematical

programming,"

Systems

Research

Center,

Case

Institute

of

Tech-

nology,

Cleveland,

Ohio,

Rept.

SRC

119-C-67-52,

1967.

[24]

A.

V.

Fiacco

and

G.

P.

McCormick,

Sequential

Unconstrained

Minimization

Techniques

for

Nonlinear

Programming.

New

York:

Wiley,

1968.

12]

R.

Fox

and

L.

Schmit,

"Advances

in

the

integrated

approach

to

structural

synthesis,"

J.

Spacecraft

and

Rockets,

vol.

3,

p.

858,

June

1966.

[261

B. P.

Dzielinski

and

R.

E.

Gomory,

"Optimal

programming

of

lot

sizes,

inventory,

and

labor

allocations,"

Management

Sci.,

vol.

11,

pp.

874-890,

July

1965.

[271

J.

E.

Falk,

"A

relaxed

interior

approach

to

nonlinear

pro-

gramming,"

Research

Analysis

Corp.,

McLean,

Va.

RAC-TP-279,

1967.

A

Formal

Basis

for

the

Heuristic

Determination

of

Minimum

Cost

Paths

PETER

E.

HART,

MEMBER,

IEEE,

NILS

J.

NILSSON,

MEMBER,

IEEE,

AND

BERTRAM

RAPHAEL

Abstract-Although

the

problem

of

determining

the

minimum

cost

path

through

a

graph

arises

naturally

in

a

number

of

interesting

applications,

there

has

been

no

underlying

theory

to

guide

the

development

of

efficient

search

procedures.

Moreover,

there

is

no

adequate

conceptual

framework

within

which

the

various

ad

hoc

search

strategies

proposed

to

date

can

be

compared.

This

paper

describes

how

heuristic

information

from

the

problem

domain

can

be

incorporated

into

a

formal

mathematical

theory

of

graph

searching

and

demonstrates

an

optimality

property

of

a

class

of

search

strate-

gies.

I.

INTRODUCTION

A.

The

Problem

of

Finding

Paths

Through

Graphs

MANY

PROBLEIVIS

of

engineering

and

scientific

importance

can

be

related

to

the

general

problem

of

finding

a

path

through

a

graph.

Examples

of

such

prob-

lems

include

routing

of

telephone

traffic,

navigation

through

a

maze,

layout

of

printed

circuit

boards,

and

Manuscript

received

November

24,

1967.

The

authors

are

with

the

Artificial

Intelligence

Group

of

the

Applied

Physics

Laboratory,

Stanford

Research

Institute,

Menlo

Park,

Calif.

mechanical

theorem-proving

and

problem-solving.

These

problems

have

usually

been

approached

in

one

of

two

ways,

which

we

shall

call

the

mathematical

approach

and

the

heuristic

approach.

1)

The

Inathematical

approach

typically

deals

with

the

properties

of

abstract

graphs

and

with

algorithms

that

prescribe

an

orderly

examination

of

nodes

of

a

graph

to

establish

a

minimum

cost

path.

For

example,

Pollock

and

Wiebensonf11

review

several

algorithms

which

are

guaran-

teed

to

find

such

a

path

for

any

graph.

Busacker

and

Saaty[2'

also

discuss

several

algorithms,

one

of

which

uses

the

concept

of

dynamic

programming.

[3]

The

mathematical

approach

is

generally

more

concerned

with

the

ultimate

achievement

of

solutions

than

it

is

with

the

computational

feasibility

of

the

algorithms

developed.

2)

The

heuristic

approach

typically

uses

special

knowl-

edge

about

the

domain

of

the

problem

being

represented

by

a

graph

to

improve

the

computational

efficiency

of

solu-

tions

to

particular

graph-searching

problems.

For

example,

Gelernter's

41

program

used

Euclidean

diagrams

to

direct

the

search

for

geometric

proofs.

Samuel[1

and

others

have

used

ad

hoc

characteristics

of

particular

games

to

reduce

100

HART

et

al.:

DETERMINATION

OF

MINIMUM

COST

PATHS

the

"look-ahead"

effort

in

searching

game

trees.

Procedures

developed

via

the

heuristic

approach

generally

have

not

been

able

to

guarantee

that

minimum

cost

solution

paths

will

always

be

found.

This

paper

draws

together

the

above

two

approaches

by

describing

how

information

from

a

problem

domain

can

be

incorporated

in

a

formal

mathematical

approach

to

a

graph

analysis

problem.

It

also

presents

a

general

algo-

rithm

which

prescribes

how

to

use

such

information

to

find

a

minimum

cost

path

through

a

graph.

Finally,

it

proves,

under

mild

assumptions,

that

this

algorithm

is

optimal

in

the

sense

that

it

examines

the

smallest

number

of

nodes

necessary

to

guarantee

a

minimum

cost

solution.

The

following

is

a

typical

illustration

of

the

sort

of

problem

to

which

our

results

are

applicable.

Imagine

a

set

of

cities

with

roads

connecting

certain

pairs

of

them.

Suppose

we

desire

a

technique

for

discovering

a

sequence

of

cities

on

the

shortest

route

from

a

specified

start

to

a

specified

goal

city.

Our

algorithm

prescribes

how

to

use

special

knowledge-e.g.,

the

knowledge

that

the

shortest

road

route

between

any

pair

of

cities

cannot

be

less

than

the

airline

distance

between

them-in

order

to

reduce

the

total

number

of

cities

that

need

to

be

considered.

First,

we

must

make

some

preliminary

statements

and

definitions

about

graphs

and

search

algorithms.

B.

Some

Definitions

About

Graphs

A

graph

G

is

defined

to

be

a

set

I

nil

of

elements

called

nodes

and

a

set

{eij}

of

directed

line

segments

called

arcs.

If

epq

is

an

element

of

the

set

{

eijj,

then

we

say

that

there

is

an

arc

from

node

np

to

node

n,

and

that

nq

is

a

successor

of

n,.

We

shall

be

concerned

here

with

graphs

whose

arcs

have

costs

associated

with

them.

We

shall

represent

the

cost

of

arc

eij

by

cij.

(An

arc

from

ni

to

nj

does

not

imply

the

existence

of

an

arc

from

nj

to

ni.

If

both

arcs

exist,

in

general

cij

cji.)

We

shall

consider

only

those

graphs

G

for

which

there

exists

8

>

0

such

that

the

cost

of

every

arc

of

G

is

greater

than

or

equal

to

6.

Such

graphs

shall

be

called

8

graphs.

In

many

problems

of

interest

the

graph

is

not

specified

explicitly

as

a

set

of

nodes

and

arcs,

but

rather

is

specified

implicitly

by

means

of

a

set

of

source

nodes

Sc

n}

and

a

successor

operator

P,

defined

on

nil},

whose

value

for

each

ni

is

a

set

of

pairs

{

(nj,

cij)

}.

In

other

words,

applying

r

to

node

ni

yields

all

the

successors

nj

of

ni

and

the

costs

cij

associated

with

the

arcs

from

ni

to

the

various

nj.

Applica-

tion

of

r

to

the

source

nodes,

to

their

successors,

and

so

forth

as

long

as

new

nodes

can

be

generated

results

in

an

explicit

specification

of

the

graph

thus

defined.

We

shall

assume

throughout

this

paper

that

a

graph

G

is

always

given

in

implicit

form.

The

subgraph

G,,

from

any

node

n

in

{

ni}

is

the

graph

defined

implicitly

by

the

single

source

node

n

and

some

r

defined

on

{ni}.

We

shall

say

that

each

node

in

G,,

is

accessible

from

n.

A

path

from

n,

to

nk

is

an

ordered

set

of

nodes

(n1,

n2,

...

,

nk)

with

each

ni+

a

successor

of

ni.

There

exists

a

path

from

ni

to

nj

if

and

only

if

nj

is

accessible

from

ni.

Every

path

has

a

cost

which

is

obtained

by

adding

the

individual

costs

of

each

arc,

ci,i+l,

in

the

path.

An

optimal

path

from

ni

to

nj

is

a

path

having

the

smallest

cost

over

the

set

of

all

paths

from

ni

to

nj.

We

shall

represent

this

cost

by

h(ni,

n3).

This

paper

will

be

concerned

with

the

subgraph

G,

from

some

single

specified

start

node

s.

We

define

a

nonempty

set

T

of

nodes

in

GU

as

the

goal

nodes.1

For

aniy

node

n

in

G.,

an

element

t

e

T

is

a

preferred

goal

node

of

n

if

and

only

if

the

cost

of

an

optimal

path

from

n

to

t

does

not

exceed

the

cost

of

any

other

path

from

n

to

any

member

of

T.

For

simplicity,

we

shall

represent

the

unique

cost

of

an

optimal

path

from

n

to

a

preferred

goal

node

of

n

by

the

symbol

h(n);

i.e.,

h(n)

=

min

h(n,t).

teT

C.

Algorithms

for

Finding

Minimun

Cost

Paths

We

are

interested

in

algorithms

that

search

G,

to

find

an

optimal

path

from

s

to

a

preferred

goal

node

of

s.

What

we

mean

by

searching

a

graph

and

finding

an

optimal

path

is

made

clear

by

describing

in

general

how

such

algorithms

proceed.

Starting

with

the

node

s,

they

generate

some

part

of

the

subgraph

G,

by

repetitive

application

of

the

suc-

cessor

operator

r.

During

the

course

of

the

algorithm,

if

P

is

applied

to

a

node,

we

say

that

the

algorithm

has

expanded

that

node.

We

can

keep

track

of

the

minimum

cost

path

from

s

to

each

node

encountered

as

follows.

Each

time

a

node

is

expanded,

we

store

with

each

successor

node

n

both

the

cost

of

getting

to

n

by

the

lowest

cost

path

found

thus

far,

and

a

pointer

to

the

predecessor

of

n

along

that

path.

Eventually

the

algorithm

terminates

at

some

goal

node

t,

and

no

more

nodes

are

expanded.

We

can

then

reConstruct

a

minimum

cost

path

from

s

to

t

known

at

the

time

of

termination

simply

by

chaining

back

from

t

to

s

through

the

pointers.

We

call

an

algorithm

admissible

if

it

is

guaranteed

to

find

an

optimal

path

from

s

to

a

preferred

goal

node

of

s

for

any

8

graph.

Various

admissible

algorithms

may

differ

both

in

the

order

in

which

they

expand

the

nodes

of

G,

and

in

the

number

of

nodes

expanded.

In

the

next

section,

we

shall

propose

a

way

of

ordering

node

expansion

and

show

that

the

resulting

algorithm

is

admissible.

Then,

in

a

fol-

lowing

section,

we

shall

show,

under

a

mild

assumption,

that

this

algorithm

uses

information

from

the

problem

represented

by

the

graph

in

an

optimal

way.

That

is,

it

expands

the

smallest

number

of

nodes

necessary

to

guar-

antee

finding

an

optimal

path.

II.

AN

ADMISSIBLE

SEARCHING

ALGORITHM

A.

Description

of

the

Algorithm

In

order

to

expand

the

fewest

possible

nodes

in

searching

for

an

optimal

path,

a

search

algorithm

must

constantly

make

as

informed

a

decision

as

possible

about

which

node

to

expand

next.

If

it

expands

nodes

which

obviously

cannot

be

on

an

optimal

path,

it

is

wasting

effort.

On

the

other

hand,

if

it

continues

to

ignore

nodes

that

might

be

oIn

an

I

We

exclude

the

trivial

case

of

s

e

T.

101

剩余7页未读，继续阅读

内容反馈

石湖一叶

粉丝: 52

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip