| Presentation | 1995/8/22 Large-scale Constraint Satisfaction Using Local-information-based Annealing and Its Parallel Processing : An Application of Emergent Computation Model CCM Yasusi Kanada, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A method for solving large-scale constraint satisfaction problems based on CCM (Chemical Casting Model), which is a model for emergent computation, is proposed in this report. A parallelized version of this method is also shown. Large-scale problems could not be solved using CCM. However, this report shows that, by introducing a method of annealing called FAM (Frustration Accumulation Method) and by adjusting the parameters appropriately, several large-scale graph coloring problems has become solvable with spending the same order of time as GSAT or simulated annealing by sequential processing using CCM. This report also shows that this method can easily be parallelized with restricted amount of mutual exclusion. The performance is almost proportional to the number of processors under certain conditions. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Emergent computation / Constraint satisfaction / Parallel processing / Annealing / Coloring Problem / Graph coloring |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | AI |
|---|---|
| Conference Date | 1995/8/22(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Large-scale Constraint Satisfaction Using Local-information-based Annealing and Its Parallel Processing : An Application of Emergent Computation Model CCM |
| Sub Title (in English) | |
| Keyword(1) | Emergent computation |
| Keyword(2) | Constraint satisfaction |
| Keyword(3) | Parallel processing |
| Keyword(4) | Annealing |
| Keyword(5) | Coloring Problem |
| Keyword(6) | Graph coloring |
| 1st Author's Name | Yasusi Kanada |
| 1st Author's Affiliation | Tsukuba Research Center, Real-World Computing Partnership() |
| Date | 1995/8/22 |
| Paper # | |
| Volume (vol) | vol.95 |
| Number (no) | 211 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |