1 of 83

בינה מלאכותית

89-5570

תרגול 2

2 of 83

חיפוש מיודע

  • עד כה ראינו אלגוריתמי חיפוש לא מיודעים.
  • חיפוש מיודע (יוריסטי) משתמש במידע נוסף על הבעיה לזירוז החיפוש.
  • מידע זה מגולם בדרך כלל בפונקציה יוריסטית, המעריכה לכל מצב את מחיר המסלול האופטימלי ממנו למטרה:

​

  • בבעיות חיפוש מסלול, פונקציה יוריסטית תעריך את המרחק של כל מצב למצב מטרה.
  • במקרה זה נעדיף להימצא במצבים בעלי ערך יוריסטי נמוך.

​

 

3 of 83

Example: Urban Navigation

  •  

 

 

4 of 83

Example: Urban Navigation

  •  

5 of 83

Example: Urban Navigation

  •  

6 of 83

מאפייני הפונקציה ההיוריסטית

שני המאפיינים החשובים ביותר:�

  • קל לחישוב
  • אומדן יחסית מדוייק של העלות כדי להגיע ליעד.
  • היוריסטיקה "טובה" יכולה להיות:� ½ opt(n)<h(n)≤opt(n)

7 of 83

היוריסטיקה מושלמת

  • יוריסטיקה מושלמת מעריכה במדויק את המרחק למטרה בדרך הזולה ביותר.

​

​

​

​

 

8 of 83

היוריסטיקה קבילה�(admissible)

  •  

 

9 of 83

היוריסטיקה מונוטונית�(consistent)

  •  

h(s)

h(s’)

 

10 of 83

Example: Urban Navigation

  •  

11 of 83

דוגמא:�9 Tile puzzle

  •  

12 of 83

דוגמא:�9 Tile puzzle

 

​

​

​

tile

0

0

0

1,2,3,4,5

2

1

1

6

3

1

2

7

1

0

1

8

האם זו יוריסטיקה קבילה...?

​

תחת האופרטורים ופונק' המחיר מקודם - התשובה היא כן.

13 of 83

דוגמא:�9 Tile puzzle

  •  

 

14 of 83

הגדרה

  •  

15 of 83

דוגמא 1#

  • בהינתן הגרף המכוון הבא, בו נקודת ההתחלה היא A ונקודת הסיום G. המספרים על הקשתות מייצגים את המחיר מעבר בין הצמתים.�בנוסף, ערכי הפו' היוריסטית הנתונים הם:

h(A) = 7

h(B) = 5

h(c) = 6

h(D) = 4

h(E) = 3

h(F) = 3

h(G) = 0

מה מבין האמרות הבאות נכון:

  1. הפו' אדמיסבילית וגם קונסיסטנטית
  2. הפו' אדמיסבילית אבל לא קונסיסטנטית
  3. הפו' קונסיסטנטית אבל לא אדמיסבילית
  4. הפו' לא אדמיסבילית ולא קונסיסטנטית

16 of 83

דוגמא 2#

  • בהינתן הגרף הבא שבו עבור חלק מהמצבים חסר הערך היוריסטי. קבעו את הטווח אפשרי עבור כל ערך היוריסטי חסר כך שהיוריסטיקה תהיה קבילה ועקבית. אם זה לא אפשרי, ציינו זאת.

​

מצב

טווח h(s)

A

≤ h(A) ≤

D

≤ h(D) ≤

E

≤ h(E) ≤

  • השלם בטבלה:

​

17 of 83

פתרון דוגמא 2#

18 of 83

Best First Search

  •  

Greedy Best First

    • f = h
    • מעדיף צומת קרוב למטרה
    • מתעלם מהמרחק אליו
    • חיפוש יוריסטי (מיודע)

Uniform Cost

    • f = g
    • מעדיף צומת קרוב לאלו שפותחו
    • מתעלם מהמרחק למטרה
    • חיפוש עיוור (לא מיודע)

19 of 83

Greedy Best First Search

    • בכל שלב בחיפוש מפתח את הצומת בעל ערך h מינימלי.
    • נמנע מביקור חוזר בצמתים.
    • האם שלם במרחבים סופיים (וקשירים)?
      • כן, כל המצבים יפותחו בסופו של דבר.
    • האם שלם במרחבים אינסופיים (וקשירים)?
      • לא. יתכן שהיוריסטיקה תטעה את
        • החיפוש ותוביל למסלול אינסופי.
    • האם אופטימלי?
      • לא!

​

I

h=5

h=6

G

h=0

5

1

7

5

20 of 83

דוגמת הרצה�Greedy

21 of 83

A Star

  •  

Greedy Best First

אלגוריתם best-first עם

f = h

Uniform Cost

אלגוריתם best-first עם

f = g

+

22 of 83

A Star Algorithm

Input:� QUEUE: Path only containing root

Algorithm:

WHILE(QUEUE not empty && first path not reach goal) DO

    • Remove first path from QUEUE
    • Create paths to all children
    • Create paths to all children
    • Add paths and sort QUEUE (by f = cost + heuristic)
    • IF QUEUE contains paths: P, Q � AND P ends in node Ni && Q contains node Ni � AND cost_P ≥ cost_Q �THEN remove P

IF goal reached THEN success ELSE failure

23 of 83

דוגמת הרצה

G

I

h = 17

h = 10

h = 13

h = 4

h = 4

h = 2

h = 1

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

24 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

h = 13

h = 4

h = 4

h = 2

h = 1

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

25 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

h = 2

h = 1

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

26 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

h = 2

h = 1

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

27 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

h = 2

g = 16

f = 18

h = 1

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

28 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

h = 2

g = 16

f = 18

h = 1

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

29 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

g = 12

f = 16

h = 2

g = 16

f = 18

h = 1

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

30 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

g = 12

f = 16

h = 2

g = 16

f = 18

h = 1

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

31 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

g = 12

f = 16

h = 2

g = 16

f = 18

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

h = 13

g = 18

f = 31

32 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

g = 12

f = 16

h = 2

g = 16

f = 18

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

G

6

33 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

g = 12

f = 16

h = 2

g = 16

f = 18

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

34 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

g = 12

f = 16

h = 2

g = 16

f = 18

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

35 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 4

g = 12

f = 16

h = 2

g = 16

f = 18

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

36 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

37 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

h = 1

g = 18

f = 19

38 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

39 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

h = 1

g = 16

f = 17

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

h = 1

g = 15

f = 16

40 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

h = 1

g = 15

f = 16

41 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

h = 0

g = 19

f =19

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

h = 1

g = 15

f = 16

h = 0

g = 18

f =18

42 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

h = 1

g = 15

f = 16

h = 0

g = 18

f =18

43 of 83

דוגמת הרצה

G

I

h = 17

g = 0

f = 17

h = 10

g = 6

f = 16

h = 13

g = 5

f = 18

h = 4

g = 10

f = 14

6

10

4

6

6

7

6

S

A

B

E

C

D

F

3

5

G

6

h = 2

g = 12

f = 14

h = 4

g = 11

f = 15

h = 1

g = 15

f = 16

h = 0

g = 18

f =18

44 of 83

תכונות A Star

שלמות – האלגוריתם שלם אם מחיר הקשתות חסום מלמטה ע"י δ > 0.

אופטימליות – האלגוריתם אופטימלי תחת התנאים הבאים:

  • Tree search A* + Admissible h
  • Graph search A* + admissible h if we allow editing of nodes in the closed list
  • Graph/Tree A* with consistent heuristic. No need to edit nodes in the closed list.

45 of 83

IDA Star

  •  

46 of 83

IDA Star�Algorithm

משתנה גלובלי

47 of 83

f-limited Search�Algorithm

המשתנה גלובלי בו משתמשים בשגרה העוטפת

 

קריאה רקורסיבית לאחר ביצוע פיתוח

48 of 83

דוגמת הרצה

h = 3

h = 0

h = 0

h = 4

h = 0

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 0

new-limit = ∞

#1

49 of 83

דוגמת הרצה

h = 3

h = 0

h = 0

g =0

f = 0

h = 4

h = 0

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 0

new-limit = ∞

#1

50 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 0

new-limit = 10

#1

51 of 83

דוגמת הרצה

h = 3

h = 0

h = 0

g =0

f = 0

h = 4

h = 0

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 10

new-limit = ∞

#2

52 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 10

new-limit = 12

#2

53 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 10

new-limit = 12

#2

54 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 10

new-limit = 11

#2

55 of 83

דוגמת הרצה

h = 3

h = 0

h = 0

g =0

f = 0

h = 4

h = 0

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 11

new-limit = ∞

#3

56 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 11

new-limit = 12

#3

57 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 11

new-limit = 12

#3

58 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 11

new-limit = 12

#3

59 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 11

new-limit = 12

#3

60 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 11

new-limit = 12

h = 4

g = 15

f = 19

#3

61 of 83

דוגמת הרצה

h = 3

h = 0

h = 0

g =0

f = 0

h = 4

h = 0

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = ∞

#4

62 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = ∞

#4

63 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = ∞

#4

64 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = ∞

#4

65 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = 19

h = 4

g = 15

f = 19

#4

66 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = 19

#4

67 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

g = 13

f = 13

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = 13

h = 0

g = 12

f = 12

#4

68 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

g = 13

f = 13

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = 13

h = 0

g = 12

f = 12

#4

69 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

g = 13

f = 13

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = 13

h = 0

g = 12

f = 12

h = 0

g = 13

f = 13

#4

70 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

g = 13

f = 13

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = 13

h = 0

g = 12

f = 12

h = 0

g = 13

f = 13

#4

71 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

g = 13

f = 13

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 12

new-limit = 13

h = 0

g = 12

f = 12

h = 0

g = 13

f = 13

h = 0

g = 14

f = 14

#4

72 of 83

דוגמת הרצה

h = 3

h = 0

h = 0

g =0

f = 0

h = 4

h = 0

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = ∞

#5

73 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = ∞

#5

74 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = ∞

#5

75 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = ∞

#5

76 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = 19

h = 4

g = 15

f = 19

#5

77 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = 19

#5

78 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

g = 13

f = 13

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = 19

h = 0

g = 12

f = 12

#5

79 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

g = 13

f = 13

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = 19

h = 0

g = 12

f = 12

#5

80 of 83

דוגמת הרצה

h = 3

g = 9

f = 12

h = 0

g = 13

f = 13

h = 0

g = 0

f = 0

h = 4

g = 8

f = 12

h = 0 g = 10

f = 10

h = 0

g = 11

f = 11

​

A

S

C

D

B

G

G

I

9

10

5

4

1

8

5

f-limit = 13

new-limit = 19

h = 0

g = 12

f = 12

#5

81 of 83

A Star�vs.�IDA Star

  • כאשר פונק' המחיר חסומה מלמטה וחיובית והיוריסטיקה קבילה:

​

​

​

שלם (אם קיים פתרון הוא מוצא כזה)

אופטימלי (אם קיים פתרון מוצא פתרון אופטימלי)

חיפוש בגרף: נמנע מפיתוחים חוזרים במצבים כאשר אין שיפור

חיפוש בעץ: מפתח מצבים חוזרים מבלי לדעת שביקר בהם בעבר

​

צריכת זיכרון לינארית באורך המסלול

82 of 83

A Star�vs.�IDA Star

  •  

...

I

g

83 of 83

A Star�vs.�IDA Star

  •