algorithm - Why do admissable heuristics guarantee optimality? -


today in class, professor introduced admissable heuristics, , stated guarantee optimality a* algorithm.

i asked him explain using extreme example make obvious, couldn't.

can please help?

we have list of candidates, right?

and each of them has etc (expected total cost) reach goal starting node (i.e. cost reach node + expected remaining cost goal (the heuristic)).

now if expected cost identical actual cost, we'll literally pick nodes on shortest path (well, of shortest paths), , nothing else. since pick lowest etc, should pretty obvious why pick nodes shortest path - not on shortest path have higher etc.

what if etc less actual cost? pick lowest etc, may end picking nodes not on shortest path. can never reach goal through path that's not shortest path because:

  • the shortest path has lower actual cost non-shortest path
  • the etc @ goal same cost reach goal via path (since we're @ goal, expected remaining cost 0)
  • the etc less or equal actual total cost on path
  • thus etc on shortest path strictly less etc @ goal reached via non-shortest path.

as example, let's have costs follows: (the cost above / below node expected remaining cost, cost @ edge actual cost)

  0    10  0  100   0 start ---- o ------ goal 0 |                 | 100   o ------ o ------ o  100  1   100  1   100

so we'd start off visiting top middle node, since etc 10 (10+0).

then goal candidate, etc of 110 (10+100+0).

then we'd pick bottom nodes 1 after other, followed updated goal, since have etc's lower etc of current goal, i.e. etc's are: 100, 101, 102, 102.

so though goal candidate, couldn't pick because there still better path out there.


Comments

Post a Comment

Popular posts from this blog

commonjs - How to write a typescript definition file for a node module that exports a function? -

consider, toml node module can use: // toml.d.ts declare module toml { export function parse(value:string):any; } declare module "toml" { export = toml; } then: /// <reference path="../../../../../defs/toml/toml.d.ts"/> import toml = require('toml'); toml.parse(...); however, node module export single function, such 'glob' ( https://github.com/isaacs/node-glob ). the node usage of module be: var glob = require("glob") glob("*.js", {}, callback(err, files) { ... }); you'd naively expect this: // glob.d.ts declare function globs(paths:string, options:any, callback:{(err:any, files:string[]):void; ...but because typescripts 'import' semantics bit strange, seems can use 'import .. = require()' statement alias modules . trying call: /// <reference path="../../../../../defs/glob/glob.d.ts"/> import blog = require('glob'); results in: error ts2072: mod
Read more

openid - Okta: Failed to get authorization code through API call -

i'm integrating okta own idp server using okta's api. i'm implementing authorization code flow following steps below: in own server, use /api/v1/authn endpoint sessiontoken. use sessiontoken obtain authorization calling endpoint: /oauth2/v1/authorize?client_id=" + clientid + "&sessiontoken=" + sessiontoken + "&response_type=code&response_mode=query&scope=openid&redirect_uri=" + redirecturl + "&state=evanyang&nonce=" it's supposed return response status code 302 , location header containing redirect url code value. however, keep getting response status code 200 , without location header, html body saying "you using unsupported browser." , "javascript disabled on browser." according api documentation: http://developer.okta.com/docs/api/resources/oidc.html#authentication-request , sessiontoken parameter sufficient this: an okta one-time sessiontoken. allows api-based
Read more

thorough guide for profiling racket code -

did googling ("racket profiling", "racket measure performance"), didn't find , there no examples in docs. did google "profile" search on htdp - no luck. (profile (f ...)) output isn't obvious other small snippets. ideally want python's python -m cprofile usage examples. when search "python profiling", both duckduckgo , google give top result: 26.4. python profilers . (although scanned quickly, seems more of reference "thorough usage guide" examples. if had else in mind, perhaps please link that?) the equivalent racket documentation be: profile: statistical profiler . a usage example: #lang racket (require profile) (profile-thunk (thunk (function-to-profile arg0 arg1) )) here (thunk e) convenience (lambda () e) . bigger example: #lang racket (module mod racket (provide f) (define (f) (for/list ([i 10000]) i))) (require (prefix-in mod: 'mod)) (define (f) (for ([i 10000
Read more